﻿// SampleCode.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>


using namespace std;

/*
* //二分 时间depth(u)+depth(v)
const int MAX_V = 10000;
vector<int> G[MAX_V];   //图的连接表示
int root;               //根节点编号

int parent[MAX_V];  //父亲节点
int depth[MAX_V];   //节点的深度


void dfs(int v, int p, int d) {
    parent[v] = p;
    depth[v] = d;
    for (int i = 0; i < G[v].size(); i++) {
        if (G[v][i] != p) dfs(G[v][i], v, d + 1);
    }
}

//预处理
void init() {
    //预处理出parent和depth
    dfs(root, -1, 0);
}

//计算v和u的lca
int lca(int u, int v) {
    //让v和u走到同一深度
    while (depth[u] > depth[v]) u = parent[u];
    while (depth[v] > depth[u]) v = parent[v];
    //让u和v走到同一节点
    while (u != v) {
        u = parent[u];
        v = parent[v];
    }
    return u;
}
*/

/*
//logn 预处理 nlogn
const int MAX_V = 10000;
const int MAX_LOG_V = 100;
vector<int> G[MAX_V];   //图的临界表示
int root;               //根节点编号

int parent[MAX_LOG_V][MAX_V];  //父亲节点
int depth[MAX_V];   //节点的深度

void dfs(int v, int p, int d) {
    parent[0][v] = p;
    depth[v] = d;
    for (int i = 0; i < G[v].size(); i++) {
        if (G[v][i] != p) dfs(G[v][i],v,d+1);
    }
}

//预处理
void init(int V) {
    //预处理parent[0] 和 depth
    dfs(root, -1, 0);
    //预处理出parent
    for (int k = 0; k + 1 < MAX_LOG_V; k++) {
        for (int v = 0; v < V; v++) {
            if (parent[k][v] < 0) parent[k + 1][v] = -1;
            else parent[k + 1][v] = parent[k][parent[k][v]];
        }
    }
}

//计算 u和v的lca
int lca(int u, int v) {
    if (depth[u] > depth[v]) swap(u, v);
    for (int k = 0; k < MAX_LOG_V; k++) {
        if (depth[v] - depth[u] >> k & 1) {
            v = parent[k][v];
        }
    }

    if (u == v)return u;
    //二分搜索
    for (int k = MAX_LOG_V; k >= 0; k--) {
        if (parent[k][u] != parent[k][v]) {
            u = parent[k][u];
            v = parent[k][v];
        }
    }
    return parent[0][u];
}
*/


/*
const int MAX_V = 10000;
const int MAX_LOG_V = 100;
vector<int> G[MAX_V];   //图的临界表示
int root;               //根节点编号

int vs[MAX_V * 2 - 1];  //dfs访问顺序
int depth[MAX_V * 2 - 1];   //节点的深度
int id[MAX_V];      //各个定点在Vs首次出现的下标


void dfs(int v, int p, int d, int& k) {
    id[v] = k;
    vs[k] = v;
    depth[k++] = d;
    for (int i = 0; i < G[v].size(); i++) {
        if (G[v][i] != p) {
            dfs(G[v][i], v, d + 1, k);
            vs[k] = v;
            depth[k++] = d;
        }
    }
}

//预处理
void init(int V) {
    int k = 0;
    dfs(root, -1, 0,k);
    //rmq_init(depth, V * 2 - 1);
}

int lca(int u, int v) {
    //return vs[query(min(id[u], id[v]), max(id[u], id[v]) + 1];
}
*/


int main()
{
    std::cout << "Hello World!\n";
}
 